/**
 * @author 汤奇
 * @version V1.0
 * @Project BookPro
 * @Package PACKAGE_NAME
 * @Description:
 * @Date 2022/7/27 20:15
 */
public class Test13 {

    public static void main(String[] args) {
        int [] arr = {5,6,8,7,2,9,1,3,4};
        Node tree = new Node();
        tree.value = arr[0];
        for (int i = 1; i < arr.length; i++) {
            insertToTree(tree,arr[i]);
        }
        printTree(tree);
    }

    /**
     * 遍历一颗二叉树
     * @param tree
     */
    private static void printTree(Node tree){
        //遍历根节点
        System.out.print(tree.value + " ");

        //遍历左子树
        if (tree.left != null)
            printTree(tree.left);

        //遍历右子树
        if (tree.right != null)
            printTree(tree.right);

    }

    private static void insertToTree(Node tree, int value){
        if (tree.value > value){
            //放左边
            if (tree.left == null){
                //于是value就作为左孩子
                tree.left = new Node();
                tree.left.value = value;
            } else {
                //把Value放入左子树中
                insertToTree(tree.left,value);
            }
        } else {
            //放右边
            if (tree.right == null){
                //于是value就作为右孩子
                tree.right = new Node();
                tree.right.value = value;
            } else {
                //把Value放入右子树中
                insertToTree(tree.right,value);
            }
        }
    }

    /**
     *定义一个无父节点线索化的二叉树节点
     */
    static class Node{
        int value;
        Node left;
        Node right;
    }
}

